package com.mj;

import java.math.BigInteger;

public class Main {

    /**
     *  斐波那契额数列的时间复杂度
     * 0 1 2 3 4 5 6 7 8(位数)
     * 0 1 1 2 3 5 8 13 21 ....
     * 求第一位加一次 0+1
     * 求第二位加一次 0+1
     * 求第三位加两次 0+1 1+1
     * 求第四位加三次 0+1 1+1 1+2
     */

    /**
     * 递归形式计算出第m位上的数
     */
    private static int fib1(int m) {
        if (m <= 1) return m;
        return fib1(m - 2) + fib1(m - 1);
    }

    /**
     * 遍历形式计算出第m位上的数
     */
    private static int fib2(int n) {
        if (n <= 1) return n;
        int first = 0;
        int second = 1;
        for (int i = 0; i < n - 1; i++) {
            int sum = first + second;
            first = second;
            second = sum;
        }
        return second;
    }


    public static void main(String[] args) {
        int a = 45;
        Times.test("fib1", new Times.Task() {
            @Override
            public void execute() {
                System.out.println(fib1(a));
                ;
            }
        });

        Times.test("fib2", new Times.Task() {
            @Override
            public void execute() {
                System.out.println(fib2(a));
            }
        });
    }

    public static void test1(int n) {
        // 汇编指令

        // 1
        if (n > 10) {
            System.out.println("n > 10");
        } else if (n > 5) { // 2
            System.out.println("n > 5");
        } else {
            System.out.println("n <= 5");
        }

        // 1 + 4 + 4 + 4
        for (int i = 0; i < 4; i++) {
            System.out.println("test");
        }

        // 14
        // 时间复杂度 O(1)
        // 空间复杂度 O(1)
    }

    public static void test2(int n) {
        // O(n)
        // 1 + 3n
        for (int i = 0; i < n; i++) {
            System.out.println("test");
        }
    }

    public static void test3(int n) {
        // 1 + 2n + n * (1 + 3n)
        // 1 + 2n + n + 3n^2
        // 3n^2 + 3n + 1
        // O(n^2)

        // O(n)
        // 1 + 2n + n * (1+2n)
        //
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }

    public static void test4(int n) {
        // 1 + 2n + n * (1 + 45)
        // 1 + 2n + 46n
        // 48n + 1
        // O(n)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 15; j++) {
                System.out.println("test");
            }
        }
    }

    public static void test5(int n) {
        // 执行次数 = log2(n)
        // O(logn)
        //2的平方
        /**
         *  假设n=8  8= 2^3   3 = log2(8) = log2
         *  假设n=16  8= 2^4  4 = log2(16)
         *
         *  第一次除 4
         *  第二次除 2
         *  第三次除 1
         */
        while ((n = n / 2) > 0) {
            System.out.println("test");
        }
    }

    public static void test6(int n) {
        // log5(n)
        // O(logn)
        while ((n = n / 5) > 0) {
            System.out.println("test");
        }
    }

    public static void test7(int n) {

        // n = 1 * 2 * 2 * 2 * 2  log2(n)

        // 1 + 2*log2(n) + log2(n) * (1 + 3n)

        // 1 + 3*log2(n) + 2 * nlog2(n)
        // O(nlogn)
        for (int i = 1; i < n; i = i * 2) {
            // 1 + 3n
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }

    public static void test10(int n) {
        //空间复杂度 O(n)
        int a = 10;
        int b = 20;
        int c = a + b;
        int[] array = new int[n];
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i] + c);
        }
    }

    public static void test11(int m, int n) {
        for (int i = 0; i < m; i++) {
            System.out.println("test");
        }
        for (int k = 0; k < n; k++) {
            System.out.println("test");
        }
    }

    public static int fib3(int n) {
        double c = Math.sqrt(5);

        return (int) ((Math.pow((1 + c) / 2, n) - Math.pow((1 - c) / 2, n)) / c);
    }
}
